import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-07-09
 * Time: 21:35
 */
public class Main {
    public static void main1(String[] args) {
        
        //TreeMap 中的常用方法 ( key , val ) 模式 ,按照key的值进行排序
        Map<String, Integer> map = new TreeMap<>();
        Set< Integer> set = new TreeSet<>();
        //1. put方法  : 往 map 中添加元素 , 不能添加重复的元素, 按照key的值进行排序
        map.put("abcd", 2);
        map.put("bkkk", 1);
        map.put("wr", 4);
        System.out.println(map);
        //2. get 方法 : 获取 map 中key值对应的 val 值
       int ret = map.get( "abcd");
        System.out.println(ret);
        //3. keySet() 方法: 把 map 中的key值放在一个集合中, 返回该集合
        Set< String> set = map.keySet();
        System.out.println(set);
        //4. (常用) entrySet方法 : 将 map 中的每一个 < key,val> 打包成一个个整体 存放到一个set中,返回该类型的set
        Set<Map.Entry<String, Integer>> entry =  map.entrySet();
        //输出返回的set
        for ( Map.Entry<String, Integer> ret2 : entry) {
            System.out.println(ret2);
        }
    }

    /**
     * LeetCode OJ : 复制带随机指针的链表  ( 实现链表的深拷贝)
     * 思路 : step1 : 遍历要复制的链表head , 使用一个 HashMap 其< key,val > 分别存储 老节点的地址 ,和新节点的地址
     *       step2 : 再次遍历要复制的链表head, 通过 map 对新节点的 next域 和 random域进行赋值 ,
     *               新节点的 next域 = map.get( cur.next)
     *               新节点的  random域 = map.get( cur.random)
     *       step : 返回新节点的头结点即可
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while( cur!= null) {
            Node node = new Node( cur.val);
            map.put( cur , node);
            cur = cur.next;
        }
        cur = head;
        while( cur!=null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }

    /**
     * 前K个高频单词
     * 思路 :
     *      step1: 先用一个map 统计每个单词出现的次数 .
     *      step2: 用一个小根堆 , 找出 前k个高频的单词 , 中间过程要处理 出现频率相同的单词 , 要按照字典序排序
     *              当出现的频率相同( map.getValue() 相等) 时, 比较 map.getKey() , 将大的放到前面. 第三步逆置后就能够按字典序排序
     *      step3 : 遍历map ,往小根堆中存放元素
     *      step4:  将小根堆的数存放到一个顺序表list中 , 然后逆置List,得到结果.
     */
    public List<String> topKFrequent(String[] words, int k) {
        Map<String , Integer> map = new HashMap<>();
        //step1: 先用一个map 统计每个单词出现的次数
        for (int i = 0; i < words.length; i++) {
            String s1 = words[i];
            //当map中没有该单词, 往其中添加,次数为1
            if( map.get(s1) == null) {
                map.put(s1,1);
            } else {   // 有该单词 ,次数+1
                int val =  map.get(s1);
                 map.put( s1,val+1);
            }
        }

        //step2: 用一个小根堆 , 找出 前k个高频的单词 , 中间过程要处理 出现频率相同的单词 , 要按照字典序排序
        //建立小根堆 , 大小为k, 类型为Map.Entry 实现比较器 , 要进行比较
        PriorityQueue< Map.Entry<String, Integer>> minheap = new PriorityQueue<>(k,new Comparator< Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if( o1.getValue().compareTo(o2.getValue()) == 0) {     //如果频率相同 , 要按照字典序排序 ,比较key的值
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());    //根据单词的频率进行比较
            }
        });

        //step3 : 遍历map ,往小根堆中存放元素
        for ( Map.Entry<String, Integer> entry: map.entrySet()) {
            //小根堆中元素个数小于k , 先往其中放
            if( minheap.size() < k) {
                minheap.offer( entry);
            } else {   // 放了k个了 , 需要和堆顶元素比较 , 频率大于堆顶元素, 堆顶元素出,新元素进
               Map.Entry<String ,Integer> top = minheap.peek();
               Integer val = top.getValue();
               //频率比堆顶元素大 , 出堆顶元素,放入新元素;
               if( entry.getValue().compareTo(val) > 0) {
                   minheap.poll();
                   minheap.offer(entry);
               } else if( entry.getValue().compareTo(val) == 0) {
                   //如果频率相同 , 要按照字典序排序 ,比较key的值
                   String key = minheap.peek().getKey();
                   if( key.compareTo( entry.getKey()) > 0) {
                        minheap.poll();
                        minheap.offer(entry);
                   }
               }
            }
        }
        //将小根堆中的结果放入list中返回.
        List< String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String key = minheap.poll().getKey();
            list.add(key);
        }
        Collections.reverse( list);
        return list;

    }

}